/*
 * @lc app=leetcode.cn id=61 lang=golang
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || k == 0 {
		return head
	}

	//计算链表长度
	l := 0
	current := head
	for current != nil {
		l++
		current = current.Next
	}

	//获取真正向右偏移量(即倒数第offset个节点)
	offset := k % l

	//查找倒数第offset个节点
	p, q := head, head
	for i := 0; i < offset; i++ {
		q = q.Next
	}

	for q.Next != nil {
		p = p.Next
		q = q.Next
	}

	//此时p倒数第offset+1节点，q是尾节点
	//连接旧链表头尾
	//新链表以倒数offset个节点为头结点，倒数offset+1个节点为尾结点
	q.Next = head
	tmp := p.Next
	p.Next = nil

	//返回新头结点
	return tmp
}

// @lc code=end

